#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size();

        vector<int> sum(n + 1, 0);  // 前缀和
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        unordered_map<int, int> cnt;  // 前缀和 的 频次

        int ret = 0;
        for (int i = 0; i <= n; i++) {
            int s = sum[i];
            ret += cnt[s - goal];
            ++cnt[s];
        }
        return ret;
    }
};

int main() {
    Solution s;

    vector<int> nums1{1, 0, 1, 0, 1};
    vector<int> nums2{0, 0, 0, 0, 0};

    int goal1 = 2;
    int goal2 = 0;

    assert(s.numSubarraysWithSum(nums1, goal1) == 4);
    assert(s.numSubarraysWithSum(nums2, goal2) == 15);

    return 0;
}